МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра ЗІ
/
Звіт до лабораторної роботи № 1
Дослідження алгоритмів архівації
з навчальної дисципліни: “ Захист програмного забезпечення ”
Мета роботи:
Розглянути основні методи стиску інформації. Навчитися на практиці реалізовувати дані алгоритми.
Теоречні відомості:
Архівація даних
Архіватор — програмне забезпечення, що використовується для об'єднання, в окремих випадках також стиснення інформації.
При збереженні, резервному копіюванні інформації тощо часто буває бажано стиснути файли так, щоб вони займали якомога менше місця. Це робиться за допомогою програм, які звуться архіваторами. Ці програми не тільки стискають інформацію в окремому файлі, але можуть і об'єднати в один архів групу файлів.
Існує багато архіваторів. Серед них найвідоміші: ARJ, DIET, ICE, LHA, LHARC, LZH, LZEXE, NARC, PAK, PKARC, PKLITE, PKXARC, PKPAK, PKZIP, PKUNZIP, RAR, ZOO. Останнім часом з'явилися програми, які, знаходячись у пам'яті комп'ютера резидентно, архівують та розархівовують «на льоту» всі файли, з якими ви працюєте, що дозволяє суттєвим чином заощаджувати простір на жорсткому диску. Такі можливості надають, наприклад, утиліта dblspace для операційної системи MS-DOS та програма DIET (T.Matsumoto, Японія).
Існує декілька методів стиснення інформації, що міститься у файлах. Мабуть, найпростішим із них є алгоритм Хоффмана, який полягає в заміні стандартних 8-бітових ASCII-кодів бітовими рядками змінної довжини в залежності від частоти використання символу так, щоб символи, що використовуються частіше, мали меншу довжину. До речі, легко зрозуміти, що у текстах найчастіше зустрічається символ «пробіл», ASCII-код якого має номер 32. Можна поширити цю ідею на пари, трійки і т. д. символів. При цьому можна одержати суттєвий виграш. Дійсно, візьміть, наприклад, дві пари символів «по» та «хщ». Ви можете назвати багато слів із першим сполученням, тоді як інше зустрічається дуже рідко. А при стандартному ASCII-кодуванні на кожне зі сполучень витрачається порівну бітів — по 16. Серед інших методів, які широко застосовуються в архіваторах для стиснення інформації у файлах можна відзначити алгоритм Лемпеля-Зіва.
Зауважимо нарешті, що комп'ютер не «розуміє» ніяких інших кодувань символів крім ASCII-кодування (чи споріднених кодувань). Тому перед використанням архівований файл повинен бути розархівованим.
Алгоритми стиснення (архівації) даних
Всі алгоритми стиснення оперують вхідним потоком даних, мінімальною одиницею яких є біт, а максимальною – декілька біт, байт або декілька байтів.
Метою процесу стиснення є отримання більш компактного вихідного потоку інформаційних одиниць з некомпактного вхідного потоку за допомогою перетворення.
Основними технічними характеристиками процесів стиснення і результатів їх роботи є :
• степінь стиснення (compress rating) або відношення (retion) об’ємів вхідного і вихідного потоків;
• швидкість стиснення – час, який витрачається на стиснення деякого об’єму інформації вхідного потоку, до отримання з нього еквівалентного вихідного потоку;
• якість стиснення – величина, яка вказує, на скільки сильно упакований вихідний потік, за допомогою застосування до нього повторного стиснення за цим або іншим алгоритмом.
Всі способи стиснення можна поділити на дві категорії: зворотнє і не зворотнє.
Під зворотнім стисненням розуміють таке перетворення вхідного потоку даних, при якому вихідний потік, в контексті певного формату даних, представляє достатньо схожий за зовнішніми характеристиками на вхідний потік об’єкт, але відрізняється від нього об’ємом. Рівень схожості вхідного і вихідного потоків визначається рівнем відповідності деяких властивостей об’єкта (тобто, стисненої і не стисненої інформації у відповідності до деякого визначеного формату даних).
Такі підходи і алгоритми використовуються для стиснення, наприклад, даних растрових графічних файлів з низькою повторюваністю байтів у потоці. При такому підході використовується власт...
